package leetcode_day._2021._202112._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/22 10:39
 * 重复叠加字符串匹配
 * 算法：字符串
 * 最小叠加次数 = b.length / a.length
 * 最大叠加次数 = 最小的叠加次数 + 1
 */
public class _22_686 {
    public static void main(String[] args) {
        System.out.println(new _22_686().strKmp("abcdabcdabcd", "cdabcdab"));
    }

    public int repeatedStringMatch(String a, String b) {
        int ans = 0;
        StringBuilder sb = new StringBuilder();
        while (sb.length() < b.length()) {
            sb.append(a);
            ++ans;
        }
        sb.append(a);
//        int idx = sb.indexOf(b);
        int idx = strKmp(sb.toString(), b);
        if (idx == -1) return -1;
        return idx + b.length() > ans * a.length() ? ans + 1 : ans;
    }
    int strKmp(String ss, String pp) {
        int n = pp.length();
        int[] next = new int[n];
        for (int i = 1, j = 0; i < pp.length(); i++) {
            while(j > 0 && pp.charAt(i) != pp.charAt(j)) j = next[j - 1];
            if (pp.charAt(i) == pp.charAt(j)) ++j;
            next[i] = j;
        }
        for (int i = 0, j = 0; i < ss.length(); i++) {
            while (j > 0 && ss.charAt(i) != pp.charAt(j)) j = next[j - 1];
            if (ss.charAt(i) == pp.charAt(j)) ++j;
            if (j == n) return i - n + 1;
        }
        return -1;
    }

}
